/*
 * Copyright (c) 2022 Huawei Device Co., Ltd.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

class Log {
    public static boolean inDebug = false;
    public static void log(String str) {
        if (inDebug) {
            System.out.println(str);
        }
    }
}

class Constants {
    public static final int DEFAULT_SIZE = 16;
    public static final int NUMBER_THIRTY = 30;
    public static final int NUMBER_SIXTEEN = 16;
    public static final int NUMBER_TWO = 2;
    public static final int NUMBER_FOUR = 4;
    public static final int NUMBER_EIGHT = 8;
    public static final double NUMBER_075PER = 0.75;
    public static final int NUMBER_THIRTYONE = 31;
    public static final int NUMBER_TEST_VALUE = 42;
    public static final int NUMBER_REPEAT_COUNT = 5;
    public static final int NUMBER_BENCHMARK_REPEAT_COUNT = 20;
    public static final int NUMBER_TIME_CUT = 1000;
}
class HashMap {
    public int calculateCapacity(int x) {
        if (x >= 1 << Constants.NUMBER_THIRTY) {
            return 1 << Constants.NUMBER_THIRTY;
        }
        if (x == 0) {
            return Constants.NUMBER_SIXTEEN;
        }
        x = x - 1;
        x |= x >> 1;
        x |= x >> Constants.NUMBER_TWO;
        x |= x >> Constants.NUMBER_FOUR;
        x |= x >> Constants.NUMBER_EIGHT;
        x |= x >> Constants.NUMBER_SIXTEEN;
        return x + 1;
    }

    public int computeHashCode(Object key) {
        if (key == null) {
            return 0;
        }
        switch (key.getClass().getName()) {
            case "java.lang.Boolean":
                return 0;
            case "java.lang.Integer", "java.lang.Double","java.lang.Long":
                return (int) key;
            case "java.lang.String":
                int h = 0;
                int len = ((String) key).length();
                for (int index = 0; index < len; index++) {
                    h = (((Constants.NUMBER_THIRTYONE * h) | 0) + ((String) key).codePointAt(index)) | 0;
                }
                return h;
            default:
                throw new Error("Internal error: Bad Java value type");
        }
    }

    public boolean equals(Object a, Object b) {
        if (!a.getClass().getName().equals(b.getClass().getName())) {
            return false;
        }
        switch (a.getClass().getName()) {
            case "java.lang.Integer", "java.lang.Double","java.lang.Long":
                return (int)a == (int)b;
            case "java.lang.Object":
                if (a == null) {
                    return b == null;
                }
                break;
            default:
                return a.equals(b);
        }
        return false;
    }

    public int capacity;
    public Integer elementCount;
    public Entry[] elementData;
    public double loadFactor;
    public int modCount;
    public int threshold;

    HashMap() {
        this(Constants.DEFAULT_SIZE, Constants.NUMBER_075PER);
    }

    HashMap(int capacity, double loadFactor) {
        this.capacity = this.calculateCapacity(capacity);
        this.elementCount = 0;
        this.elementData = new Entry[this.capacity];
        this.loadFactor = loadFactor;
        this.modCount = 0;
        this.computeThreshold();
    }

    public void computeThreshold() {
        this.threshold = (int)(this.elementData.length * this.loadFactor) | 0;
    }

    public void clear() {
        if (this.elementCount == null) {
            return;
        }
        this.elementCount = 0;
        for (int i = this.elementData.length; i >= 0; i--) {
            this.elementData[i] = null;
        }
        this.modCount++;
    }

    public HashMap clone() {
        HashMap result = new HashMap(this.elementData.length, this.loadFactor);
        result.putAll(this);
        return result;
    }

    public boolean containsValue(int value) {
        for (Entry entry : this.elementData) {
            Entry currentEntry = entry;
            while (currentEntry != null) {
                if (this.equals(value, currentEntry.value)) {
                    return true;
                }
                currentEntry = entry.next;
            }
        }
        return false;
    }

    public EntrySet entrySet() {
        return new EntrySet(this);
    }

    public Integer get(int key) {
        Entry entry = this.getEntry(key);
        if (entry != null) {
            return entry.value;
        }
        return null;
    }

    public Entry getEntry(int key) {
        int hash = this.computeHashCode(key);
        int index = hash & (this.elementData.length - 1);
        return this.findKeyEntry(key, index, hash);
    }

    public Entry findKeyEntry(int key, int index, int keyHash) {
        Entry entry = this.elementData.length == 0 ? null : this.elementData[index];
        while (entry != null && (entry.origKeyHash != keyHash || !this.equals(key, entry.key))) {
            entry = entry.next;
        }
        return entry;
    }

    public boolean isEmpty() {
        return this.elementCount == 0;
    }

    public Integer put(int key, int value) {
        int hash = this.computeHashCode(key);
        int index = hash & (this.elementData.length - 1);
        Entry entry = this.findKeyEntry(key, index, hash);
        if (entry == null) {
            this.modCount++;
            entry = this.createHashedEntry(key, index, hash);
            this.elementCount += 1;
            if (this.elementCount > this.threshold) {
                this.rehash(0);
            }
        }
        Integer result = entry.value;
        entry.value = value;
//         if (Log.inDebug) {
//             if ( key % 10000 == 0) {
//                 Log.log("put:" + entry);
//             }
//         }
        return result;
    }

    public Entry createHashedEntry(int key, int index, int hash) {
        Entry entry = new Entry(key, hash, null);
        entry.next = this.elementData[index];
        this.elementData[index] = entry;
        return entry;
    }

    public void putAll(HashMap map) {
        if (map.isEmpty()) {
            return;
        }
        ValueIterator iterator = map.entrySet().iterator();
        while (iterator.hasNext()) {
            Entry entry = iterator.next();
            this.put(entry.key, entry.value);
        }
    }

    public void rehash(int capacity) {
        if (capacity <= 0) {
            capacity = this.elementData.length;
        }
        int length = calculateCapacity(capacity == 0 ? 1 : capacity << 1);
        Entry[] newData = new Entry[length];
        for (int i = 0; i < this.elementData.length; ++i) {
            Entry entry = this.elementData[i];
            this.elementData[i] = null;
            while (entry != null) {
                int index = entry.origKeyHash & (length - 1);
                Entry next = entry.next;
                entry.next = newData[index];
                newData[index] = entry;
                entry = next;
            }
        }
        this.elementData = newData;
        this.computeThreshold();
    }

    public Integer remove(int key) {
        Entry entry = this.removeEntryForKey(key);
        if (entry == null) {
            return null;
        }
        return entry.value;
    }

    public void removeEntry(Entry entry) {
        int index = entry.origKeyHash & (this.elementData.length - 1);
        Entry current = this.elementData[index];
        if (current == entry) {
            this.elementData[index] = entry.next;
        } else {
            while (current.next != entry) {
                current = current.next;
            }
            current.next = entry.next;
        }
        this.modCount++;
        this.elementCount--;
    }

    public Entry removeEntryForKey(int key) {
        int hash = computeHashCode(key);
        int index = hash & (this.elementData.length - 1);
        Entry entry = this.elementData[index];
        Entry last = null;
        while (entry != null && !(entry.origKeyHash == hash && this.equals(key, entry.value))) {
            last = entry;
            entry = entry.next;
        }
        if (entry == null) {
            return null;
        }
        if (last == null) {
            this.elementData[index] = entry.next;
        } else {
            last.next = entry.next;
        }
        this.modCount++;
        this.elementCount--;
        return entry;
    }

    public int size() {
        return this.elementCount;
    }

    public ValueCollection values() {
        return new ValueCollection(this);
    }
}

class Entry {
    public int key;
    public Integer value;
    public int origKeyHash;
    public Entry next;

    Entry(int key, int hash, Integer value) {
        this.key = key;
        this.value = value;
        this.origKeyHash = hash;
    }

    public Entry clone() {
        Entry result = new Entry(this.key, this.value, this.origKeyHash);
        if (this.next != null) {
            result.next = this.next.clone();
        }
        return result;
    }
    @Override
    public String toString() {
        return this.key + "=" + this.value;
    }

    public int getKey() {
        return this.key;
    }

    public int getValue() {
        return this.value;
    }
}

class AbstractMapIterator {
    public HashMap associatedMap;
    public int expectedModCount = 0;
    public Entry futureEntry = null;
    public Entry currentEntry = null;
    public Entry prevEntry = null;
    public int position = 0;

    AbstractMapIterator(HashMap map) {
        this.associatedMap = map;
        this.expectedModCount = map.modCount;
    }

    public boolean hasNext() {
        if (this.futureEntry != null) {
            return true;
        }
        while (this.position < this.associatedMap.elementData.length) {
            if (this.associatedMap.elementData[this.position] == null) {
                this.position++;
            } else {
                return true;
            }
        }
        return false;
    }

    public void checkConcurrentMod() {
        if (this.expectedModCount != this.associatedMap.modCount) {
            throw new Error("Concurrent HashMap modification detected");
        }
    }

    public void makeNext() {
        this.checkConcurrentMod();
        if (!this.hasNext()) {
            throw new Error("No such element");
        }
        if (this.futureEntry == null) {
            this.currentEntry = this.associatedMap.elementData[this.position++];
            this.futureEntry = this.currentEntry.next;
            this.prevEntry = null;
            return;
        }
        if (this.currentEntry != null) {
            this.prevEntry = this.currentEntry;
        }
        this.currentEntry = this.futureEntry;
        this.futureEntry = this.futureEntry.next;
    }

    public void remove() {
        this.checkConcurrentMod();
        if (this.currentEntry == null) {
            throw new Error("Illegal state");
        }
        if (this.prevEntry == null) {
            int index = this.currentEntry.origKeyHash & (this.associatedMap.elementData.length - 1);
            this.associatedMap.elementData[index] = this.associatedMap.elementData[index].next;
        } else {
            this.prevEntry.next = this.currentEntry.next;
        }
        this.currentEntry = null;
        this.expectedModCount++;
        this.associatedMap.modCount++;
        this.associatedMap.elementCount--;
    }
}

class ValueIterator extends AbstractMapIterator {

    ValueIterator(HashMap map) {
        super(map);
    }

    public Entry next() {
        this.makeNext();
        return this.currentEntry;
    }
}

class EntrySet {
    public HashMap associatedMap;

    EntrySet(HashMap map) {
        this.associatedMap = map;
    }

    public int size() {
        return this.associatedMap.elementCount;
    }

    public void clear() {
        this.associatedMap.clear();
    }

    public ValueIterator iterator() {
        return new ValueIterator(this.associatedMap);
    }
}

class ValueCollection {
    public HashMap associatedMap;

    ValueCollection(HashMap map) {
        this.associatedMap = map;
    }

    public boolean contains(int object) {
        return this.associatedMap.containsValue(object);
    }

    public int size() {
        return this.associatedMap.elementCount;
    }

    public void clear() {
        this.associatedMap.clear();
    }

    public ValueIterator iterator() {
        return new ValueIterator(this.associatedMap);
    }
}

/*
 * @State
 * @Tags Jetstream2
 */
class Benchmark {
    public void run() {
        HashMap map = new HashMap();
        int COUNT = 90000;
        for (int i = 0; i < COUNT; i++) {
            map.put(i, Constants.NUMBER_TEST_VALUE);
        }
        int result = 0;
        for (int j = 0; j < Constants.NUMBER_REPEAT_COUNT; j++) {
            for (int i = 0; i < COUNT; i++) {
                result += map.get(i);
//                 if (Log.inDebug) {
//                   if (i % 10000 == 0) {
//                     int value = map.get(i);
//                     Log.log("get:" + i + "=" + value);
//                   }
//                 }
            }
        }

        int keySum = 0;
        int valueSum = 0;
        ValueIterator iterator = map.entrySet().iterator();
        while (iterator.hasNext()) {
            Entry entry = iterator.next();
            keySum += entry.key;
            valueSum += entry.value;
        }
    }

    /**
     * @Benchmark
     */
    public void runIteration() {
        double startTime = System.nanoTime() / 1_000_000.0;
        for (int j = 0; j < Constants.NUMBER_BENCHMARK_REPEAT_COUNT; ++j) {
            this.run();
        }
        double endTime = System.nanoTime() / 1_000_000.0;
        double time = endTime - startTime;
        System.out.println("hash-map: ms = " + time);
    }

    public static void main(String[] args) {
        new Benchmark().runIteration();
    }
}



